#include <iostream>

using namespace std;
// 328. 奇偶链表
// 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
// 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
// 输入：head = [1,2,3,4,5]
// 输出：1,3,5,2,4]

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL || head->next == NULL)  // 链表为空或者只有一个节点
            return head;
        ListNode* p = head, *q, *r, *tail;

        ListNode* h = new ListNode(0);  // 存放偶数结点的链表 h
        r = h;  // r来处理偶数结点的链表，指向其尾部
        p = head;   // p 遍历原链表
        while(p != NULL)
        {
            tail = p;   // tail 记录原来单链表的尾节点
            q = p->next;    // q指向偶数结点
            if(q != NULL) {
                p->next = q->next;  // 删除结点q
                r->next = q; r = q; // 采用尾插法插入到h中
                p = p->next;
            }
            else
                break;  // 结点p为尾结点时结束
        }
        r->next = NULL;

        tail->next = h->next;   // 将偶数序号的单链表连接到原链表的尾部
        return head;
    }
};

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
